Flip columns for max number of equal rows

Time: O(MxN); Space: O(MxN); medium

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

Example 1:

Input: matrix =

[
    [0,1],
    [1,1]
 ]

Output: 1

Explanation:

  • After flipping no values, 1 row has all values equal.

Example 2:

Input: matrix =

[
    [0,1],
    [1,0]
]

Output: 2

Explanation:

  • After flipping values in the first column, both rows have equal values.

Example 3:

Input: matrix =

[
    [0,0,0],
    [0,0,1],
    [1,1,0]
]

Output: 2

Explanation:

  • After flipping values in the first two columns, the last two rows have equal values.

Notes:

  • 1 <= len(matrix) <= 300

  • 1 <= len(matrix[i]) <= 300

  • All len(matrix[i]) are equal

  • matrix[i][j] is 0 or 1

[4]:

import collections

class Solution1(object):
    def maxEqualRowsAfterFlips(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        count = collections.Counter(tuple(x^row[0] for x in row)
                                          for row in matrix)
        return max(list(count.values()))

[5]:

s = Solution1()
matrix = [
    [0,1],
    [1,1]
 ]
assert s.maxEqualRowsAfterFlips(matrix) == 1
matrix = [
    [0,1],
    [1,0]
]
assert s.maxEqualRowsAfterFlips(matrix) == 2
matrix = [
    [0,0,0],
    [0,0,1],
    [1,1,0]
]
assert s.maxEqualRowsAfterFlips(matrix) == 2